#include "stdafx.h"


// klasa reprezentujaca graf skierowany
class CGraph {

public:
	// przy definiowaniu grafu ustalamy czy ma on korzystac
	// z macierzy sasiedztwa czy z listy nastepnikow
	enum Type {

		Matrix = 0,		// korzystanie z macierzy sasiedztwa
		Lists = 1		// korzystanie z listy nastepnikow
	};
	enum GType {

		UnDirect = 0,	// losowanie dla grafu nieskierowanego
		Direct = 1		// losowanie dla grafu skierowanego
	};

public:
	// konstruktor
	CGraph( int _cV, int _cE, Type _type );
	// destruktor
	~CGraph();


	// wypelnia macierz losowymi wartosciami
	int ** RandomMatrix(GType _gtype);
	// zwraca ilosc wierzcholkow
	int GetCountV();
	// zwraca ilosc krawedzi
	int GetCountE();
	// zwraca wage krawedzi z wierzcholka vSrc do wierzcholka vDst
	int GetWeight( int vSrc, int vDst );
	// zwraca tablice nastepnikow danego wierzcholka v
	std::vector< int > GetConsequents( int v );
	// dodaje krawedz skierowana o wadze weight
	// z wierzcholka vSrc do wierzcholka vDst
	bool AddDirectEdge( int vSrc, int vDst, int weight );
	// dodaje krawedz nieskierowana o wadze weight
	// miedzy wierzcholkami vSrc i vDst
	bool AddUndirectEdge( int vA, int vB, int weight );
	// dodaje krawedz skierowana o wadze weight
	// z wierzcholka vSrc do wierzcholka vDst
	// mozna tu podac takze wage ujemna
	bool AddDirectNegEdge( int vSrc, int vDst, int weight );
	// sprawdza czy w grafie jest ujemny cykl
	bool HaveNegCycle();
	// sprawdza czy graf jest spojny
	bool IsConnected();
	// wypelnia drzewo krawedzi na podstawie macierzy/listy
	void FillEdgesTree();

	void StartClock();
	void StopClock();

	/* Algorytmy */
	// uruchamia algorytm dijkstra dla wierzcholka u
	// zwraca tablice d z odleglosciami miedzy wierzcholkami
	int * Dijkstra( int u );
	// uruchamia algorytm bellmana-forda dla wierzcholka u
	// zwraca tablice d z odleglosciami miedzy wierzcholkami
	int * BellmanFord( int u );
	// uruchamia algorytm kruskala
	// zwraca fige
	void Kruskal();
	// uruchamia algorytm prima dla wierzcholka u
	// zwraca banana
	void Prim(int u);
	

private:
	// metoda przeszukujaca graf
	void DFS( bool * connected, std::vector< int > consequents );

private:
	// ilosc wierzcholkow
	int cV;
	// ilosc krawedzi
	int cE;
	// typ przechowywania informacji o polaczeniach
	int type;

	// struktura krawedzi A-B i wagi
	// przeciazony operator porownania, porownuje tylko wagi
	struct edge {

		int vA;
		int vB;
		int weight;

		bool operator < ( const edge &other ) const {

			// sprawdzane sa numery wierzcholkow
			if( weight == other.weight ) {

				if( vA == other.vA ) {

					return vB < other.vB;

				} else {
					
					return vA < other.vA;
				}

			} else {	// w przeciwnym wypadku sprawdzane sa wagi

				return weight < other.weight;
			}
		}
	};

	// drzewo krawedzi
	std::set< edge > edges;

	// macierz sasiedztwa
	int ** gMatrix;
	// listy nastepnikow
	std::vector< std::vector< struct edge > > gLists;
};